
class Solution {

  public static void main(String[] args) {
    //

    Node tail1 = new Node(new Random().nextInt(100), null);
    Node tail2 = new Node(new Random().nextInt(100), tail1);
    Node tail3 = new Node(new Random().nextInt(100), tail2);
    Node tail4 = new Node(new Random().nextInt(100), tail3);
    Node tail5 = new Node(new Random().nextInt(100), tail4);
    Node tail6 = new Node(new Random().nextInt(100), tail5);
    Node tail7 = new Node(new Random().nextInt(100), tail6);

    Node head = tail7;

    while (head != null)
    {
      System.out.print(head.val + "\t");
      head = head.next;
    }
    System.out.println();

    sortList(tail7, null);

    head = tail7;

    while (head != null)
    {
      System.out.print(head.val + "\t");
      head = head.next;
    }
    System.out.println();
  }

  public static void quick_sort(int[] a, int start, int end)
  {
    if(start >= end)
      return;
    int flag = a[start];
    int left = start;
    int right = end;

    while(left < right)
    {
      while (a[right] >= flag && left < right)   //等号很关键
        right--;
      a[left] = a[right];
      while(a[left] <= flag && left < right)
        left++;
      a[right] = a[left];
    }
    a[left] = flag;

    quick_sort(a, start, left-1);
    quick_sort(a, left+1, end);
  }

  public static void quick_sort2(int[] a, int start, int end)
  {
    if(start >= end)
      return;
    int flag = a[start];
    int left = start;
    int right = end;

    while(left < right)
    {
      while (a[right] >= flag && left < right)
        right--;
      while(a[left] <= flag && left < right)
        left++;

      if(left < right)
      {
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;
      }
    }

    a[start] = a[left];
    a[left] = flag;

    quick_sort(a, start, left-1);
    quick_sort(a, left+1, end);
  }

  public static void sortList(Node node, Node endflag)
  {
    Node  small = node;
    if(small == null || node == endflag)
      return;

    Node big = node.next;

    while(big != endflag)
    {
      if(big.val <= node.val)
      {
        small = small.next;
        int temp = small.val;
        small.val = big.val;
        big.val = temp;
      }
      big = big.next;
    }
    int temp = small.val;
    small.val = node.val;
    node.val = temp;

    sortList(node, small);
    sortList(small.next, endflag);
  }
}